1. Field
The present application relates to a method for symmetrically routing traffic in a network. More particularly, the present application relates to a method for building both forward and reverse paths in the network similar using a stateful routing mechanism.
2. Brief Description of the Related Art
Routing is the act of moving information across a computer network from a source to a destination. Along the way, at least one intermediate node is typically encountered. Routing occurs at the network layer (or Layer 3). Routing protocols use metrics to evaluate what path will be the best for a packet to travel. A metric is a standard of measurement, such as a path bandwidth, that is used by routing algorithms to determine the optimal path to a destination. To aid the process of path determination, routing algorithms initialize and maintain routing tables, which contain the routing information. Routing information varies depending on the routing algorithm used.
Routing tables contain information used by switching software to select the best route. Routing algorithms fill routing tables with a variety of information including a destination address and a next hop. An association between the destination address and the next hop tells a router that a particular destination can be reached optimally by sending the packet to a particular router representing the “next hop” on the path to the final destination. When a router receives an incoming packet, it checks the destination address and attempts to associate this address with the next hop. Routing tables may further contain additional information, such as data about the desirability of a path. Optimal routes are then determined by a comparison of metrics, as defined by each particular routing algorithm.
The routers communicate with one another and maintain their routing tables through the transmission of a variety of messages. A routing update message is one such message that generally consists of all or a portion of a routing table. By analyzing routing updates from all other routers, a router can build a detailed picture of network topology. A link-state advertisement, another example of a message sent between routers, informs other routers of the state of the sender's links. Link information also can be used to build a complete picture of network topology to enable routers to determine optimal routes to network destinations.
Routing algorithms have used many different metrics to determine the best route. Sophisticated routing algorithms can base route selection on multiple metrics by combining these metrics in a single (hybrid) metric. Examples of metrics used include path length, reliability, delay, bandwidth, load, and communication cost. Symmetrical routing is usually not a requirement for standard routing protocols/algorithms, and upper layers of the network have been designed with this assumption. Thus, asymmetrical routes are common in the real-world Internet.
Symmetrical routing uses the same forward and reverse path. Even if link costs are symmetrical, studies having shown that most routing protocols make no effort to compute symmetrical routes. Thus, most paths through the Internet are routed asymmetrically, providing significantly different forward and reverse paths. For example, if multiple shortest path routes exist, arbitrary tiebreakers can lead to asymmetrical routes. In some cases, routing protocols deliberately compute asymmetrical routes because of policy constraints.
One of the only ways for upper layers of the network to enforce symmetrical routing is to use Internet Protocol (IP) source routing, but almost no network backbone operator supports that option. Source routing is an IP option that allows the originator of a packet to specify what path that packet will take in the forward direction, and what path return packets sent back to the originator will take. Source routing is useful when the default route of a connection fails or is suboptimal for some reason, or for network diagnostic purposes. Traceroute is a program currently available that may be used for tracing forward network paths, which may be useful for network diagnostics. Traceroute provides the ability to track the route of packets from a first host to a second host, but only for the forward path. It is not possible to assume that the reverse path is the same. Therefore, it is difficult to analyze problems, even using Traceroute when the two paths are different. In order to use Traceroute to analyze problems, the capability to issue traceroute commands from the remote device is required to see the backward path.
Most standard routing protocols deal well with asymmetrical link costs for computing routes between a single source and a single destination; however, many multicast routing algorithms tacitly assume link asymmetry. Current routing protocols do not take into account symmetrical path requirements. Routing symmetry is important, especially for some applications, such as Network Time Protocol (NTP) and Multicast Backbone (MBONE), which depend on symmetrical routing. Thus, an efficient symmetric routing method is desirable.